/**
 * 反转单链表
 */

public class ReverseList {
  /**
   * 反转链表
   * 
   * @param head
   * @return
   */
  public static Node reverseList1(Node head) {
    if ((head == null) || (head.next == null)) {
      return head;
    }
    Node reHead = null;// 定义新链表头结点
    while (head != null) {
      Node cur = head.next;// 记录下一个节点
      head.next = reHead;// 将rehead节点连接到head节点上
      reHead = head;// 让rehead指向head
      head = cur;// 将head指向下一个节点
    }
    return reHead;
  }
  /**
   * 递归反转链表
   * 
   * @param head
   * @return
   */
  public static Node reverseList2(Node head) {
    if ((head == null) || (head.next == null)) {
      return head;
    }
    Node rehead = reverseList2(head.next);
    head.next.next = head;// 将头节点置于末端
    head.next = null;// 防止链表循环
    return rehead;
  }
  /**
   * 打印链表
   * 
   * @param head
   */
  public static void printList(Node head) {
    if (head == null) {
      return;
    }
    while (head != null) {
      System.out.print(head.val + " ");
      head = head.next;
    }    
    System.out.println();    
  }
  /**
   * 测试
   * 
   * @param args
   */
  public static void main(String[] args) {
    Node n1 = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    Node n4 = new Node(4);
    Node n5 = new Node(5);
    n1.next = n2;
    n2.next = n3;
    n3.next = n4;
    n4.next = n5;
    System.out.println("非递归法: ");
    System.out.println("翻转前：");
    printList(n1);
    Node rehead1 = reverseList1(n1);    
    System.out.println("翻转后：");
    printList(rehead1);
    System.out.println();

    Node n6 = new Node(6);
    Node n7 = new Node(7);
    Node n8 = new Node(8);
    Node n9 = new Node(9);
    Node n10 = new Node(10);
    n6.next = n7;
    n7.next = n8;
    n8.next = n9;
    n9.next = n10;
    System.out.println("递归法: ");
    System.out.println("翻转前：");
    printList(n6);
    Node rehead2 = reverseList2(n6);
    System.out.println("翻转后：");
    printList(rehead2);
    System.out.println();
  }
}
